#pragma once
#include<iostream>
#include<vector>
using namespace std;

//OpenHash封装实现
namespace OpenHash {

    template<class T>
    struct HashNode {
        HashNode(const T& data)
            :_data(data)
            ,_next(nullptr)
        {}


        HashNode<T>* _next;
        T _data;
    };


    template<class K>
    struct Hash
    {
        size_t operator()(const K& key) //返回键值key
        {
            return key;
        }
    };


    //string类型的特化
    template<>
    struct Hash<string> {
        //BKDRHash算法
        size_t operator()(const string& s) {
            size_t value = 0;
            for (auto ch : s) {
                value += ch;
                value *= 131;
            }
            return value;
        }
    };

    //前置声明
    template <class K, class T, class KeyOfT, class HashFunc>
    class HashTable;

    template <class K, class T, class KeyOfT, class HashFunc = Hash<K>>
    struct __HTIterator {
        typedef HashNode<T> Node;
        typedef __HTIterator<K, T, KeyOfT, HashFunc> Self;
        typedef HashTable< K, T, KeyOfT, HashFunc> HT;
        Node* _node;
        HT* _pht;

        __HTIterator(Node* node, HT* pht)
            :_node(node)
            ,_pht(pht)
        {}


        Self& operator++() {
            //当前桶中还有数据，走到当前桶结点的下一个
            if (_node->_next){
                _node = _node->_next;
            }
            //当前桶中没有数据了，走到下一个桶
            else {
                HashFunc hf;
                KeyOfT kot;

                //size_t index = HashFunc()(KeyOfT()(_node->_data)) % _pht->_table.size();
                size_t index = hf(kot(_node->_data)) % _pht->_table.size();

                ++index;
                while (index < _pht->_table.size()) {
                    if (_pht->_table[index]) {
                        _node = _pht->_table[index];
                        return *this;
                    }
                    else {
                        ++index;
                    }
                }
                _node = nullptr;  
            }
            return *this;
        }

        T& operator*() {
            return _node->_data;
        }

        T* operator->() {
            return &_node->_data;
        }

        bool operator !=(const Self& s) const{
            return _node != s._node;
        }

        bool operator ==(const Self& s) const {
            return _node == s._node;
        }
    };


    template <class K, class T, class KeyOfT, class HashFunc = Hash<K>>
    class HashTable {
        typedef HashNode<T> Node;
        friend struct __HTIterator<K, T, KeyOfT, HashFunc>;
    public:
        typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator;
        
        HashTable() = default; //显示生成默认构造函数

        HashTable(const HashTable& ht) {
            _n = ht._n;
            _table.resize(ht._table.size());

            for (size_t i = 0; i < ht._table.size(); i++) {
                Node* cur = ht._table[i];
                while (cur) {
                    Node* copy = new Node(cur->_data);
                    copy->_next = _table[i];
                    _table[i] = copy;
                    cur = cur->_next;
                }
            }
        }

        HashTable& operator=(HashTable ht) {
            _table.swap(ht._table);
            swap(_n, ht._n);

            return *this;
        }

        ~HashTable() {
            for (size_t i = 0; i < _table.size(); i++) {
                Node* cur = _table[i];
                while (cur) {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                _table[i] = nullptr;
            }
        }



        iterator begin() {
            size_t i = 0;
            while (i < _table.size()) {
                if (_table[i]) {
                    return iterator(_table[i], this);
                }
                ++i;
            }
            return end();
        }

        iterator end() {
            return iterator(nullptr, this);
        }

        size_t GetNextPrime(size_t prime){
            static const int PRIMECOUNT = 28;
            static const size_t primeList[PRIMECOUNT] = {
                53ul, 97ul, 193ul, 389ul, 769ul,
                1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
                49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
                1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
                50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
                1610612741ul, 3221225473ul, 4294967291ul
            };
            size_t i = 0;
            for (; i < PRIMECOUNT; ++i){
                if (primeList[i] > prime)
                    return primeList[i];
            }
            return primeList[i];
        }



        pair<iterator, bool> Insert(const T& data) {
            HashFunc hf;
            KeyOfT kot;

            auto ret = Find(kot(data));
            if (ret != end()) {
                return make_pair(ret, false);
            }

            //负载因子到1时增容
            if (_n == _table.size()) {
                vector<Node*> newtable;

                /*size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
                newtable.resize(newSize, nullptr);*/

                newtable.resize(GetNextPrime(_table.size()));

                //遍历取旧表中结点，重新计算映射位置，挂到新表中
                for (size_t i = 0; i < _table.size(); ++i) {
                    if (_table[i]) {
                        Node* cur = _table[i];
                        while (cur) {
                            //计算key在新表中的映射位置
                            Node* next = cur->_next;
                            size_t index = hf(kot(cur->_data)) % newtable.size();
                            //头插
                            cur->_next = newtable[index];
                            newtable[index] = cur;
                            cur = next;
                        }
                        _table[i] = nullptr;
                    }
                }
                _table.swap(newtable);
            }

            //计算key映射位置
            size_t index = hf(kot(data)) % _table.size();
            Node* newnode = new Node(data);

            //头插
            newnode->_next = _table[index];
            _table[index] = newnode;

            ++_n;

            return make_pair(iterator(newnode, this), true);
        }

        iterator Find(const K& key) {
            KeyOfT kot;
            HashFunc hf;
            if (_table.size() == 0) {
                return end();
            }

            size_t index = hf(key) % _table.size();
            Node* cur = _table[index];

            while (cur) {
                if (kot(cur->_data) == key) {
                    return iterator(cur, this);
                }
                else {
                    cur = cur->_next;
                }
            }
            return end();
        }


        bool Erase(const K& key) {
            HashFunc hf;
            size_t index = hf(key) % _table.size();

            Node* cur = _table[index];
            Node* prev = nullptr;

            while (cur) {
                if (kot(cur->_data) == key) {
                    if (prev == nullptr) {
                        //头删
                        _table[index] = cur->_next;                       
                    }
                    else {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    --_n;
                    return true;
                }
                else {
                    prev = cur;
                    cur = cur->_next;
                }
            }
            return false;
        }


    private:
        vector<Node*> _table;
        size_t _n;
    };
}